package com.LeeCode;

import java.util.TreeMap;

/**
 * 无需开会的工作日
 */

public class Code3169 {
    public static void main(String[] args) {
        int[][] meetings = {
                {5, 7},
                {1, 3},
                {9, 10}
        };
        System.out.println(new Code3169().countDays(10, meetings));
    }

    public int countDays(int days, int[][] meetings) {
        TreeMap<Integer, Integer> map = new TreeMap<>();

        // 记录会议区间的差分变化
        for (int[] meet : meetings) {
            int start = meet[0];
            int end = meet[1];
            map.put(start, map.getOrDefault(start, 0) + 1);
            map.put(end + 1, map.getOrDefault(end + 1, 0) - 1);
        }

        int res = 0;
        int curr = 0;
        int prevDay = 1;

        // 遍历所有事件点
        for (int key : map.keySet()) {
            if (key > days) break; // 超出范围不用处理

            // 空闲区间 [prevDay, key)
            int freeDays = Math.min(key - prevDay, days - prevDay + 1);
            if (curr == 0 && freeDays > 0) {
                res += freeDays;
            }

            // 更新当前并发会议数
            curr += map.get(key);
            prevDay = key;
        }

        // 最后检查是否还有剩余天数未处理
        if (prevDay <= days) {
            int freeDays = days - prevDay + 1;
            if (curr == 0) {
                res += freeDays;
            }
        }

        return res;
    }
}
